package LeetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LC30 {
    /**
     * 字典完全匹配的必要条件：字典中所有单词的长度之和与字符串长度相同
     * 使用移动指针和字典长度截取字符串中一段，将问题简化为：总长度相同时，能否由字典中所有单词组合构成指定字符串
     * 将字典数组转化为map便于检索，键为单词，值为单词在字典出现的总次数（允许单词重复出现）
     * 另外，生成首字母开头的单词长度最大值map，例如，a开头的字母在字典中出现的单词最大长度为5，
     * 则在匹配单词失败时，不用一直移动尾指针到整个字符串末尾，只需根据首字母找到单词最大长度，指针在此处及时终止搜索。
     * 在搜索到某一个单词时，需在map中对计数减1，若此时为0，则移除此键，当所有单词匹配完，map为空，说明完全匹配
     */
    public List<Integer> findSubstring(String s, String[] words) {
        Map<String, Integer> wordCountMap = new HashMap<String, Integer>(); // 单词计数
        Map<Character, Integer> maxLenMap = new HashMap<Character, Integer>(); // 字典中每个起始字母对应的的最长单词长度

        int total = 0;
        for (String word : words) {
            Character c = word.charAt(0);
            int len = word.length();
            total += len; // 字典总字符数

            if (null == maxLenMap.get(c)) {
                maxLenMap.put(c, len);
            } else if (len > maxLenMap.get(c)) {
                maxLenMap.put(c, len);
            }

            if (wordCountMap.containsKey(word)) {
                wordCountMap.put(word, wordCountMap.get(word) + 1);
            } else {
                wordCountMap.put(word, 1);
            }
        }

        List<Integer> positionList= new ArrayList<>();
        for (int start = 0; start <= s.length() - total; start++) {
            String segment = s.substring(start, start + total);
            boolean matched = find(segment, wordCountMap, maxLenMap);
            if (matched) {
                positionList.add(start); // 完全匹配
            }
        }

        return positionList;
    }

    private boolean find(String text, Map<String, Integer> wordCountMap, Map<Character, Integer> maxLenMap) {
        Map<String, Integer> dictMap = new HashMap(wordCountMap);

        Integer maxLen = maxLenMap.get(text.charAt(0));
        if (null == maxLen){// 字典中没有这个字母开头的单词，中断本次匹配
            return false;
        }

        // 当前单词不超过len
        for (int q = 1; q <= maxLen; q++) {
            String word = text.substring(0, q);
            Integer num = dictMap.get(word);
            if (null == num) {
                continue;
            }

            // 字典中存在此单词，继续匹配当前串的余下部分
            if (num > 1) {
                dictMap.put(word, num - 1);
            } else {
                dictMap.remove(word); // 此单词在字典中出现次数用完
                if (dictMap.isEmpty()) {
                    return true;
                }
            }

            // 递归处理余下子串
            boolean matched = find(text.substring(q), dictMap, maxLenMap);
            if (matched) {
                return true;
            } else {
                // 本轮不匹配，还原map，移动指针扩大单词长度继续尝试
                dictMap.put(word, num);
            }
        }

        return false;
    }
}